/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：丑数 II</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/ugly-number-ii/
 * </pre>
 * <p>创建日期：2019年11月28日上午9:28:21</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code264UglyNumberii</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code264UglyNumberii
{
	public static void main(String[] args)
	{
		/**
		 * 编写一个程序，找出第 n 个丑数。

		丑数就是只包含质因数 2, 3, 5 的正整数。

		示例:

		输入: n = 10
		输出: 12
		解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
		说明:  

		1 是丑数。
		n 不超过1690。

		 */
		int nthUglyNumber = nthUglyNumber03Point(1600);
		System.out.println(nthUglyNumber);
	}

	/**
	 * 3指针的方法
	 * 如果按照大小顺序排列的话，那么当前丑数一定是之前某个丑数乘以质因子的结果，且是质因子乘积中最小的那个
	 * @param n
	 * @return
	 */
	public static int nthUglyNumber03Point(int n)
	{
		long[] result = new long[n];
		result[0] = 1;
		int r2 = 0, r3 = 0, r5 = 0, index = 1;
		long min;
		while (index < n)
		{
			min = Math.min(result[r2] * 2, Math.min(result[r3] * 3, result[r5] * 5));
			if (min == result[r2] * 2)
			{
				r2++;
			}
			if (min == result[r3] * 3)
			{
				r3++;
			}
			if (min == result[r5] * 5)
			{
				r5++;
			}
			result[index] = min;
			index++;
		}
		return (int) result[n - 1];
	}

	/**
	 * 陷阱：
	 * 	如果使用int类型数组，过程中的数值计算可能超出int类型导致为负数，导致最终计算结果不准
	 * 精彩方法：
	 * 	可以使用3指针
	 * @param n
	 * @return
	 */
	public static int nthUglyNumber(int n)
	{
		int[] _dp = new int[] { 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 };
		if (n <= 10)
		{
			return _dp[n - 1];
		} else
		{
			long[] dp = new long[n];
			for (int i = 0; i < _dp.length; i++)
			{
				dp[i] = _dp[i];
			}
			for (int i = 10; i < dp.length; i++)
			{
				long min = dp[i - 1];
				long dpi = 0;
				for (int j = 3; j < i; j++)
				{
					/**
					 * 这里其实可以改进，改进的话，就成了三指针法了
					 * 因为假如找dp[i]对应的是dp[j]*2,那么下次找dp[i+1],dp[j]*2就一定不是，那么就没必要再循环取一次，则应该取dp[j+1]*2
					 * 以此类推乘以3和5的情况
					 */
					long dpV2 = dp[j] * 2;
					long dpV3 = dp[j] * 3;
					long dpV5 = dp[j] * 5;
					long tempMin = dpV2 > min ? dpV2 : (dpV3 > min ? dpV3 : (dpV5 > min ? dpV5 : dpi));
					dpi = dpi == 0 ? tempMin : Math.min(tempMin, dpi);
				}
				dp[i] = dpi;
			}
			return (int) dp[n - 1];
		}
	}
}
